package Offer;
/*
* 根据二分法计算原理，至少要保证变量 res 可以正确存储 1000000007^2,所以用long
*

* */
public class Offer14cuttingRope {
    public int cuttingRope(int n) {
        if(n == 2)
            return 1;
        if(n == 3)
            return 2;
        int res = 1;
        while(n > 4){
            res *= 3;
            res%=1000000007;
            n -= 3;
        }
        return (int)(res * n % 1000000007);
    }
}
